package 剑指offer.Month7_07.day18;

public class 连续子数组的最大和 {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int max = array[0];//记录最终的最大的数组和
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int left = 0,right = 0;
        int resl = 0,resr = 0;
        for (int i = 1; i < array.length; i++) {
            right++;
            dp[i] = Math.max(array[i] + dp[i - 1], array[i]);
            if(dp[i - 1] + array[i] < array[i]) left = right;
            if(dp[i] > max || (dp[i] == max && (right - left + 1) > (resr - resl + 1))){
                max = dp[i];
                resl = left;
                resr = right;
            }
        }
        int[] res = new int[resr - resl + 1];
        for (int i = resl; i <= resr; i++) {
            res[i - resl] = array[i];
        }
        return res;
    }
}
